/*
* swap.c
*
*  Created on: 2012-6-27
*  Author: zyh
*/


#include "vm/swap.h"
#include "threads/malloc.h"
#include "threads/thread.h"
#include "userprog/pagedir.h"
#include "kernel/list.h"
#include "filesys/file.h"
#include "filesys/filesys.h"
#include "lib/string.h"
#include "filesys/cache.h"

#define SE_SIZE (sizeof(struct swap_entry))		//swap entry所占的字节
#define SECTORS_PER_SLOT (PGSIZE / BLOCK_SECTOR_SIZE)    //每个slot所占的扇区数

static struct list swap_table;        //swap表
static struct block* sw_device;        //用于存放swap的磁盘块
static struct bitmap *free_slot;      /* 空闲的slot, one bit per slot. */

/*
 * [zyh]初始化，在init.c中调用
 */
void swap_init()
{
    list_init(&swap_table);
    lock_init(&swap_lock);
    sw_device = block_get_role(BLOCK_SWAP);			//从磁盘中拿到swap
    free_slot = bitmap_create(block_size(sw_device) / SECTORS_PER_SLOT);	//给free_slot分配固定大小的空间
    if (free_slot == NULL)
        PANIC ("bitmap creation failed--swap device is too large");
}

/*
 * [zyh]
* 根据page_number找到相应的swap_entry
* 如果没有找到，返回null
*/
static struct swap_entry* swap_find(struct thread *t,uintptr_t page_number)
{
    struct list_elem* e;
    struct swap_entry* se;
    for(e = list_begin(&swap_table); e != list_end(&swap_table); e = list_next(e)){
        se = list_entry(e,struct swap_entry,elem);
       if(se->page_number == page_number && se->owner == t){
            return se;
        }
    }
    return NULL;
}

/*
 * ［zyh]
* 创建一个swap_entry,victim为牺牲的帧，start为起始扇区
*/
void swap_create_entry(struct FTE* victim,block_sector_t start)
{
    struct swap_entry* new_evictee;
    new_evictee = (struct swap_entry*)malloc(SE_SIZE);
    new_evictee->owner = victim->owner_thread;
    new_evictee->page_number = victim->owner_page_number;
    new_evictee->start = start;
    new_evictee->writable = pagedir_is_writable(victim->owner_thread->pagedir,
    		pgno_to_va(victim->owner_page_number));
    list_push_back(&swap_table,&new_evictee->elem);
}

/*
 * [zyh]
* 创建一个空闲的slot，起始扇区地址为sectorp
*/
static bool free_slot_allocate (block_sector_t *sectorp)
{
	 block_sector_t sector = bitmap_scan_and_flip (free_slot, 0, 1, false);

	 if (sector != BITMAP_ERROR){
	   *sectorp = sector;
	 }
	 return sector != BITMAP_ERROR;
}

/*
 * [zyh]
* 释放掉一个slot，起始扇区为sector
*/
static void free_slot_release (block_sector_t sector)
{
 ASSERT (bitmap_all (free_slot, sector, 1));
 bitmap_set_multiple(free_slot, sector,1, false);
}

/*
 * [zyh]
 * 把buffer中的内容写到swap中，start为起始扇区，共写PGSIZE大小的内容
 */
static inline void write_to_block(void* buffer,block_sector_t start)
{
    uint8_t i;
    for(i = 0; i < SECTORS_PER_SLOT; i++){			//写出swap中
        //block_write(sw_device,start * SECTORS_PER_SLOT + i,buffer + i * BLOCK_SECTOR_SIZE);
    	write_to_cache(sw_device,start * SECTORS_PER_SLOT + i,0,BLOCK_SECTOR_SIZE,buffer + i * BLOCK_SECTOR_SIZE);
    }
}

/*
 * [zyh]
 * 把swap中的内容读到buffer，start为起始扇区，共读PGSIZE大小的内容
 */
static inline void read_from_block(void* buffer,block_sector_t start)
{
    uint8_t i;
    for(i = 0; i < SECTORS_PER_SLOT; i++){
    	//block_read(sw_device,start * SECTORS_PER_SLOT + i,buffer + i * BLOCK_SECTOR_SIZE);
    	read_from_cache(sw_device,start * SECTORS_PER_SLOT + i,0,BLOCK_SECTOR_SIZE,buffer + i * BLOCK_SECTOR_SIZE);
    }
}


/*
 * [zyh],[zpj]
 * 用于页面置换
 */
bool swap_replace(uintptr_t page_number,bool stack)
{
    bool writable = true;		//是否可写
    struct FTE* victim;			//要换出去的帧
    struct swap_entry* evictee;		//被逐出的swap entry
    struct swap_entry* want;		//想要的swap entry
    void* buffer;				//要写到swap中的缓冲区

    lock_acquire(&swap_lock);
    victim = select_frame();	//根据CLOCK算法拿到牺牲的帧

    if (victim->owner_thread == NULL)	//如果该帧空闲，直接使用，不需要swap
    {
        evictee = NULL;
    }
    else
    {
        evictee = swap_find(victim->owner_thread,victim->owner_page_number);	//找到被逐出的swap entry
        page_unmap(victim->owner_thread,victim->owner_page_number);			//解除映射
    }

    buffer = pgno_to_va(victim->frame_number);			//被逐出者的页面缓冲
    want = swap_find(thread_current(),page_number);		//找到需要页面的swap entry

    if(victim->owner_thread != NULL)
    {
        if(evictee == NULL){        //如果在swap table中没有找到被逐出者，则创建一项
            block_sector_t sector = 0;
            if(free_slot_allocate(&sector)){    //申请一个slot
            	write_to_block(buffer,sector);			//写到swap
                swap_create_entry(victim,sector);    //新建一项
            }else{
                lock_release(&swap_lock);		//没有申请到
                return false;
            }
        }else{        //如果找到而且页面被修改过，则要写到swap中
            if(pagedir_is_dirty(victim->owner_thread->pagedir,buffer)){
            	write_to_block(buffer,evictee->start);
            }
        }
    }

    if (want != NULL)		//如果在swap table中找到需要的frame，则直接从swap中读出来
    {
    	read_from_block(pgno_to_va(victim->frame_number),want->start);
        writable = want->writable;
        free_slot_release(want->start);    //读完之后，释放这个slot
        list_remove(&want->elem);
        free(want);
    }
    else if(stack)
    {
        writable = true;
    }
    else
    {
        struct exe_map *em = NULL;
        struct list_elem *e;
        for (e=list_begin(&thread_current()->exe_list); e!=list_end(&thread_current()->exe_list); e=list_next(e))
        {
            em = list_entry(e,struct exe_map,elem);
            if (pg_no(em->upage) == page_number)
                break;
        }
        if (e == list_end(&thread_current()->exe_list))
        {
            lock_release(&swap_lock);
            return false;
        }
        else
        {
            if (em->read_bytes == 0)
            {
                memset (pgno_to_va(victim->frame_number),0,PGSIZE);
            }
            else
            {
                file_seek(thread_current()->elf,em->file_offset);
                file_read(thread_current()->elf,pgno_to_va(victim->frame_number),PGSIZE);
                if (em->read_bytes < PGSIZE){
                    memset (pgno_to_va(victim->frame_number) + em->read_bytes,0,PGSIZE - em->read_bytes);
                }
            }
            writable = em->writable;
        }
    }

    //重新建立映射
    if(page_map(&thread_current()->SPT,page_number,victim->frame_number,writable) == SP_SUCCESS)
    {
    	unregist_frame(victim->frame_number);
        regist_frame(victim->frame_number,page_number);
        lock_release(&swap_lock);
        return true;
    }else{
        lock_release(&swap_lock);
        return false;
    }
}

/*
 * [zyh]
 * 当进程退出时，调用该函数，清除它在swap中的空间
 */
void swap_free_slot(struct thread* t)
{
    struct list_elem* e;
    struct list_elem* tmp_elem;
    struct swap_entry* evictee;
    for(e = list_begin(&swap_table); e != list_end(&swap_table); ){
        evictee = list_entry(e,struct swap_entry,elem);
        if(evictee->owner == t){
            free_slot_release(evictee->start);        //如果该线程在swap中有slot，则释放该slot
            tmp_elem = e;
            e = list_next(tmp_elem);
            list_remove(tmp_elem);
            free(evictee);
        }else{
            e = list_next(e);
        }
    }
}
